package linkedList;

/**
 * 回文链表 -234
 *
 * @author yyz
 * @create 2023-11-23 13:37
 */
public class 回文链表 {
    /*
        1.找中间点
        2.反转
        3.与原链表值比较
     */
    public boolean isPalindrome2(ListNode h) {
        //找中间点
        ListNode p1 = h;
        ListNode p2 = h;
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }
        ListNode middle = p1;

        //反转
        ListNode n1 = null;
        while (middle != null) {
            ListNode o2 = middle.next;
            middle.next = n1;
            n1 = middle;
            middle = o2;
        }
        ListNode reverse = n1;

        while (reverse != null) {
            if (reverse.val != h.val) {
                return false;
            }
            reverse = reverse.next;
            h = h.next;
        }
        return true;
    }

    //优化后
    public boolean isPalindrome(ListNode h) {
        ListNode p1 = h;
        ListNode p2 = h;
        ListNode n1 = null;
        ListNode o1 = h;
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;

            o1.next = n1;
            n1 = o1;
            o1 = p1;
        }
        if (p2 != null && p2.next == null) {
            p1 = p1.next;
        }

        while (n1 != null) {
            if (n1.val != p1.val) {
                return false;
            }
            n1 = n1.next;
            p1 = p1.next;
        }
        return true;
    }

    public static void main(String[] args) {
        ListNode list = ListNode.of(1, 2, 3, 2, 2, 1);
        System.out.println(new 回文链表().isPalindrome(list));
//        System.out.println(new 回文链表().reverseList(list));
    }
}
